# 2022-6-27

from utils.array_utils import check_all


def merge_01(arr1, arr2):
    i1 = i2 = 0
    arr3 = []
    while i1 < len(arr1) and i2 < len(arr2):
        if arr1[i1] < arr2[i2]:
            arr3.append(arr1[i1])
            i1 += 1
        else:
            arr3.append(arr2[i2])
            i2 += 1
    while i1 < len(arr1):
        arr3.append(arr1[i1])
        i1 += 1
    while i2 < len(arr2):
        arr3.append(arr2[i2])
        i2 += 1
    return arr3


def merge_02(arr1, arr2):
    arr3 = []
    while arr1 and arr2:
        if arr1[0] < arr2[0]:
            # print(arr1)
            arr3.append(arr1.pop(0))
        else:
            arr3.append(arr2.pop(0))
    if arr1:
        arr3 += arr1
    if arr2:
        arr3 += arr2
    return arr3


def merge_sort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    # print(left, right)
    # print(merge_sort(left))
    # print(merge_sort(right))
    # return merge_02(merge_sort(left), merge_sort(right))
    return merge_01(merge_sort(left), merge_sort(right))


def swap(l, a, b):
    l[a], l[b] = l[b], l[a]


if __name__ == '__main__':
    ll = [5, 2, 4, 9, 1, 0]
    l1 = [1, 3, 5]
    l2 = [2, 4, 5, 9, 20]
    # hl(ll, 0, 5)
    # partition_01(ll)
    # print(merge_02(l1, l2))
    # print(merge_sort(ll))
    print(check_all(merge_sort, 500))
